
function main(nodes, sides) {
  let {getPrevIds,getNextIds} = getConnectedNodeIds(sides);
  straighten(nodes, getPrevIds, getNextIds).forEach(row => {
      console.log(row.map(n => n && n.id));    
  })
}


// 根据id查找指向该id的id数组
function getConnectedNodeIds(sides) {
  let idMaps = sides.reduce((obj, d) => {
    if (!obj[d.from]) obj[d.from] = { prev: [], next: []};
    if (!obj[d.to]) obj[d.to] = { prev: [], next: []};
    obj[d.to].prev.push(d.from);
    obj[d.from].next.push(d.to);
    return obj;
  }, {});
  return {
    getPrevIds(id) {
      return idMaps[id] ? idMaps[id].prev || [] : [];
    },
    getNextIds(id) {
      return idMaps[id] ? idMaps[id].next || [] : [];
    }
  };
}

// 扩充每层节点数
function expandNodesPosition(nodes) {
  let maxOrder = nodes.reduce((m, n) => (m > n.length ? m : n.length), 0);

  nodes.forEach((row, i) => { 
      if (row.length < maxOrder) {
          nodes[i] = expandArr(row, maxOrder)
      }   
  })
}

// 拉直
function straighten(nodes, getPrevIds, getNextIds) {
  expandNodesPosition(nodes)

  // 待优化，通过判断中间层是否有交换，有则再执行一次
  while(arrangeNodeByPrev(nodes, getPrevIds) == true) {1}
  while(arrangeNodeByNext(nodes, getNextIds) == true) {1}

  return nodes;
}

// 排列每层节点的位置
function arrangeNodeByPrev(nodes, getPrevIds) {
  // 是否还要再调整，默认false
  let again = false
  let len = nodes.length;
  while (len && len--) {
    let curRankNodes = nodes[len];
    
    // 首层需要单独处理
    if (len == 0) {
      return again
    }
    
    curRankNodes.forEach((node, cIndex) => {
      if (!node) return;

      let tIndex = getTargetIndex(nodes[len - 1], node, getPrevIds)
      
      if (cIndex != tIndex && !curRankNodes[tIndex]) {
        nodes[len] = swap(curRankNodes, cIndex, tIndex)
        // 如果是中间层有交换，则要再调整
        if (len < nodes.length - 1) { again = true }
      }
    });
  }
  return again
}

function arrangeNodeByNext(nodes, getNextIds) {
  let again = false
  nodes.forEach((nodeArr, rank) => {
    if (rank == nodes.length - 1) {
      return
    }

    let len = nodeArr.length
    while (len && len --) {
      if (!nodeArr[len]) continue;

      let tIndex = getTargetIndex(nodes[rank + 1], nodeArr[len], getNextIds, 'isTop')
      if (tIndex == -1) {
        return;
      }
      if (len != tIndex && !nodeArr[tIndex]) {
        nodes[rank] = swap(nodeArr, len, tIndex)
        // 如果是中间层有交换，则要再调整
        if (rank > 0) { again = true }
      }
    }
  })
  return again
}

function swap(arr, i, j) {
  let tmp = arr[i];
  arr[j] = tmp;
  arr[i] = null;
  return arr
}

// 获取相连节点(prev|next)的索引
function getTargetIndex(rankNodes, node, getLinkNodeIds, isTop) {
  let ids = getLinkNodeIds(node.id);
  let indexArr = [];

  if (ids.length == 0) return -1;

  rankNodes.forEach((rnode, pIndex) => {
    if (!rnode) return;
    if (ids.includes(rnode.id)) {
      indexArr.push(pIndex);
    }
  });

  // indexArr.sort((a, b) => a - b)

  // 取中间位置
  // 2|3|4|50 -> (2+50)/2 :这是从上向下调整时的计算？
  // 2|3|4|5 -> 3
  // 2|3|5 -> 3
  // 2|3|4 -> 3
  // 1|2 -> 1
  // 1|3 -> 2
  // 3 -> 3
  if (isTop && indexArr.length > 1) {
    return Math.floor((indexArr[0] + indexArr[indexArr.length - 1]) / 2);
  }
  return indexArr[Math.floor(indexArr.length / 2)];
}


function expandArr(arr, maxOrder) {
  return arr.concat(new Array(maxOrder - arr.length).fill(null));
}


function test1() {
  let nodes = [
    [
      { id: "A", rank: -3 },
      { id: "B", rank: -3 },
    ],
    [
      { id: "J", rank: -2 },
      { id: "C", rank: -2 },
      { id: "D", rank: -2 },
      { id: "E", rank: -2 },
    ],
    [
      { id: "F", rank: -1 },
      { id: "G", rank: -1 },
      { id: "H", rank: -1 },
    ],
    [{ id: "I", rank: 0 }],
  ];
  let sides = [
    { id: "s1", from: "A", to: "C" },
    { id: "s2", from: "A", to: "D" },
    { id: "s1-1", from: "A", to: "J" },
    { id: "s3", from: "B", to: "E" },
    { id: "s4", from: "C", to: "F" },
    { id: "s5", from: "D", to: "G" },
    { id: "s6", from: "E", to: "H" },
    { id: "s7", from: "H", to: "I" },
  ];

  main(nodes, sides)
}

console.log('---------------test1---------------------')

test1()

console.log('---------------test2---------------------')

function test2() {
  let nodes = [
    [
      { id: "A", rank: -3 },
      { id: "B", rank: -3 },
      { id: "K", rank: 0 }
    ],
    [
      { id: "J", rank: -2 },
      { id: "C", rank: -2 },
      { id: "D", rank: -2 },
      { id: "E", rank: -2 },
      { id: "M", rank: -2 },
    ],
    [
      { id: "F", rank: -1 },
      { id: "G", rank: -1 },
      { id: "H", rank: -1 },
    ],
    [{ id: "I", rank: 0 }],
  ];
  let sides = [
    { id: "s1", from: "A", to: "C" },
    { id: "s2", from: "A", to: "D" },
    { id: "s1-1", from: "A", to: "J" },
    { id: "s3", from: "B", to: "E" },
    { id: "s3", from: "B", to: "J" },
    { id: "s3", from: "B", to: "M" },
    { id: "s4", from: "C", to: "F" },
    { id: "s5", from: "D", to: "G" },
    { id: "s6", from: "E", to: "H" },
    { id: "s7", from: "H", to: "I" },
    { id: "s8", from: "F", to: "I" },
    { id: "s9", from: "G", to: "I" },
  ];

  main(nodes, sides)
}

test2()

console.log('---------------test3---------------------')

function test3() {
  main([], [])
}
test3()
console.log('---------------test4---------------------')

function test4() {
  let nodes = [
    [
      { id: "A", rank: -3 },
    ],
    [
      { id: "B", rank: -2 },
      { id: "C", rank: -2 },
    ],
    [
      { id: "D", rank: -1 },
      { id: "E", rank: -1 },
      { id: "F", rank: -1 },
      { id: "G", rank: -1 }
    ],
  ];
  let sides = [
    { id: "s1", from: "A", to: "B" },
    { id: "s2", from: "A", to: "C" },
    { id: "s3", from: "B", to: "D" },
    { id: "s3", from: "B", to: "E" },
    { id: "s3", from: "C", to: "F" },
    { id: "s4", from: "C", to: "G" },
  ];
  main(nodes, sides)
}
test4()
console.log('---------------test5---------------------')

function test5() {
  let nodes = [
    [
      { id: "A", rank: -3 },
    ],
    [
      { id: "B", rank: -2 },
    ]
  ];
  let sides = [
    { id: "s1", from: "A", to: "B" },
  ];
  main(nodes, sides)
}
test5()
console.log('---------------test6---------------------')
